import math
import random

random.seed(42)


def assign_cluster(x, c):
    min_dist = float('inf')  # 初始化最小距离为无穷大
    cluster_idx = 0  # 初始化聚类索引
    for idx, center in enumerate(c):
        dist = math.sqrt(sum((xi - ci) ** 2 for xi, ci in zip(x, center)))
        if dist < min_dist:
            min_dist = dist
            cluster_idx = idx
    return cluster_idx


def Kmeans(data, k, epsilon=1e-3, iteration=100):
    if not isinstance(data, list) or len(data) == 0:
        raise ValueError("输入样本集data必须是非空列表")
    if not all(isinstance(sample, list) for sample in data):
        raise ValueError("样本集中每个元素必须是特征列表")
    sample_dim = len(data[0])
    if not all(len(sample) == sample_dim for sample in data):
        raise ValueError("所有样本必须具有相同的特征维度")
    if not isinstance(k, int) or k <= 0:
        raise ValueError("聚类数量k必须是正整数")

    data_len = len(data)
    if k >= data_len:
        raise ValueError(f"聚类数量k({k})不能大于等于样本数量({data_len})")

    # 步骤1：初始化聚类中心（从数据集中随机选k个不同样本）
    center_indices = random.sample(range(data_len), k)
    centers = [data[idx].copy() for idx in center_indices]

    # 步骤2：迭代更新聚类中心与样本分配
    for iter_num in range(iteration):
        cluster_labels = [assign_cluster(sample, centers) for sample in data]

        new_centers = []
        for cluster_idx in range(k):
            cluster_samples = [
                data[sample_idx] for sample_idx in range(data_len)
                if cluster_labels[sample_idx] == cluster_idx
            ]

            if not cluster_samples:
                # 从有样本的聚类中随机选一个样本作为新中心
                valid_samples = [data[i] for i in range(data_len) if cluster_labels[i] != cluster_idx]
                new_center = valid_samples[random.randint(0, len(valid_samples) - 1)].copy()
            else:
                # 按特征维度求均值（适配任意特征维度）
                new_center = [
                    sum(sample[dim] for sample in cluster_samples) / len(cluster_samples)
                    for dim in range(sample_dim)
                ]
            new_centers.append(new_center)

        center_changes = []
        for new_c, old_c in zip(new_centers, centers):
            # 计算单个中心的欧氏变化量
            change = math.sqrt(sum((new_c[dim] - old_c[dim]) ** 2 for dim in range(sample_dim)))
            center_changes.append(change)

        if max(center_changes) < epsilon:
            print(f"迭代{iter_num + 1}次后收敛")
            break

        # 未收敛则更新中心，进入下一轮迭代
        centers = new_centers
    else:
        print(f"达到最大迭代次数{iteration}，未完全收敛(最大中心变化量:{max(center_changes):.6f})")

    # 步骤3：返回最终结果（聚类中心+样本标签）
    final_labels = [assign_cluster(sample, centers) for sample in data]
    return centers, final_labels


if __name__ == "__main__":
    test_data = [
        [1, 2], [2, 1], [1, 1], [2, 2],
        [5, 6], [6, 5], [5, 5], [6, 6],
        [9, 10], [10, 9], [9, 9], [10, 10]
    ]

    try:
        final_centers, final_labels = Kmeans(test_data, k=3)
        print("最终聚类中心:")
        for idx, center in enumerate(final_centers, 1):
            print(f"  聚类{idx}:{[round(val, 4) for val in center]}")
        print("各样本聚类标签:")
        print(f"  {final_labels}")
    except ValueError as e:
        print(f"运行出错：{e}")
